﻿namespace LeetCodeProject._0001_1000._101_200._101_110._109;

public class Solution
{
    public TreeNode SortedListToBST(ListNode head)
    {
        var count = 0;
        var node = head;
        while (node != null)
        {
            count++;
            node = node.next;
        }

        return SortedListToBST(ref head, count);
    }

    private TreeNode SortedListToBST(ref ListNode head, int count)
    {
        if (count == 0)
            return null;
        var left = SortedListToBST(ref head, count / 2);
        var root = new TreeNode(head.val)
        {
            left = left
        };
        head = head.next;
        root.right = SortedListToBST(ref head, count - count / 2 - 1);
        return root;
    }
}